{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[![Jupyter Notebook预览](https://cdn.jsdelivr.net/gh/eternidad33/picbed/img/upyter%E9%A2%84%E8%A7%88.png)](https://nbviewer.jupyter.org/github/eternidad33/csp/blob/master/Python/题解汇总/第3题题解汇总.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 目录\n",
    "\n",
    "- [最大的矩形](#最大的矩形)\n",
    "- [命令行选项](#命令行选项)\n",
    "- [字符串匹配](#字符串匹配)\n",
    "- [集合竞价](#集合竞价)\n",
    "- [节日](#节日)\n",
    "- [模板生成系统](#模板生成系统)\n",
    "- [画图](#画图)\n",
    "- [路径解析](#路径解析)\n",
    "- [炉石传说](#炉石传说)\n",
    "- [权限查询](#权限查询)\n",
    "- [Markdown](#Markdown)\n",
    "- [JSON查询](#JSON查询)\n",
    "- [Crontab](#Crontab)\n",
    "- [URL映射](#URL映射)\n",
    "- [元素选择器](#元素选择器)\n",
    "- [CIDR合并](#CIDR合并)\n",
    "- [损坏的RAID5](#损坏的RAID5)\n",
    "- [字符画](#字符画)\n",
    "- [化学方程式](#化学方程式)\n",
    "- [Markdown渲染器](#Markdown渲染器)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 最大的矩形\n",
    "\n",
    "试题编号：\t201312-3  \n",
    "试题名称：\t最大的矩形\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def 最大的矩形(count, l):\n",
    "    \"\"\"思路：遍历每个矩形向左右延伸的最大面积\"\"\"\n",
    "    b = []  # 储存所有局部最大矩形\n",
    "    for i in range(count):\n",
    "        width = 0  # 矩形宽度\n",
    "        for j in reversed(range(i)):  # 向左（反转）搜索左边高度不小于矩形i高度的\n",
    "            if l[j] >= l[i]:\n",
    "                width += 1  # 加左边宽度\n",
    "            else:\n",
    "                break\n",
    "        for j in range(i, count):  # 向右搜索高度不小于矩形i高度的\n",
    "            if l[j] >= l[i]:\n",
    "                width += 1  # 加右边宽度（含矩形i自身）\n",
    "            else:\n",
    "                break\n",
    "        b.append(l[i] * width)  # 得到包含矩形i自身的局部最大矩形面积\n",
    "    print(max(b))  # 从所有局部最大矩形选出全局最大举行\n",
    "\n",
    "# n = int(input())\n",
    "# a = list(map(int, input().split()))\n",
    "# 最大的矩形(n, a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 命令行选项\n",
    "\n",
    "试题编号：\t201403-3  \n",
    "试题名称：\t命令行选项\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def 命令行选项(ops, count, cmd_list):\n",
    "    ops += \" \"\n",
    "    global i\n",
    "    uop = []  # 存储无参选项\n",
    "    hop = []  # 存储有参选项\n",
    "    for i in range(len(ops) - 1):\n",
    "        if ops[i + 1] == \":\":\n",
    "            hop.append(ops[i])\n",
    "        else:\n",
    "            uop.append(ops[i])\n",
    "    for i in range(count):\n",
    "        # 将命令分割\n",
    "        cmd = cmd_list[i]\n",
    "        d = {}\n",
    "        j = 1\n",
    "        while j < len(cmd):\n",
    "            # 如果为参数选项\n",
    "            if cmd[j][0] == \"-\" and len(cmd[j]) == 2:\n",
    "                if cmd[j][1] in uop:  # 无参选项处理\n",
    "                    d[cmd[j][1]] = \"#\"\n",
    "                    j += 1\n",
    "                elif cmd[j][1] in hop and j + 1 < len(cmd):  # 有参选项处理\n",
    "                    d[cmd[j][1]] = cmd[j + 1]\n",
    "                    j += 2\n",
    "                else:  # 其他选项错误退出循环\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        keys = list(set(d.keys()))\n",
    "        keys.sort()\n",
    "        print(\"Case \" + str(i + 1) + \":\", end=\"\")\n",
    "        for key in keys:\n",
    "            print(\" -\" + key, end=\"\")\n",
    "            if d[key] != \"#\":\n",
    "                print(\" \" + d[key], end=\"\")\n",
    "        print()\n",
    "\n",
    "\n",
    "# options = input()\n",
    "# n = int(input())\n",
    "# cmds = []\n",
    "# for i in range(n):\n",
    "#     cmds.append(list(input().split()))\n",
    "# 命令行选项(options, n, cmds)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 字符串匹配\n",
    "\n",
    "试题编号：\t201409-3  \n",
    "试题名称：\t字符串匹配\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def 字符串匹配(s0, c, ss):\n",
    "    # 区分大小写\n",
    "    if c == 1:\n",
    "        for s in ss:\n",
    "            if s0 in s:\n",
    "                print(s)\n",
    "    else:\n",
    "        for s in ss:\n",
    "            if s0.lower() in s.lower():\n",
    "                print(s)\n",
    "\n",
    "\n",
    "# s1 = input()\n",
    "# flag = int(input())\n",
    "# n = int(input())\n",
    "# ls = []\n",
    "# for i in range(n):\n",
    "#     ls.append(input())\n",
    "# 字符串匹配(s1, flag, ls)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 集合竞价\n",
    "\n",
    "试题编号：\t201412-3  \n",
    "试题名称：\t集合竞价\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#!/usr/bin/python3\n",
    "# -*- coding:utf-8 -*-\n",
    "\"\"\"\n",
    "@author: Vigilr\n",
    "@file: 集合竞价.py\n",
    "@date: 2020-08-26\n",
    "@Editor: PyCharm\n",
    "@desc: \n",
    "\"\"\"\n",
    "# 集合竞价\n",
    "# cancel是从前往后执行的，不能取消cancel\n",
    "import sys\n",
    "\n",
    "\n",
    "def 集合竞价():\n",
    "    global count\n",
    "    records = []\n",
    "    delList = []\n",
    "    for line in sys.stdin:\n",
    "        record = list(line.split())\n",
    "        records.append(record)\n",
    "    # 根据cancel清除记录\n",
    "    for record in records:\n",
    "        if record[0] == \"cancel\":  # 用数组记录并del可能会删除两遍发生错误\n",
    "            record[0] = \"\"\n",
    "            records[int(record[1]) - 1][0] = \"\"  # 将要删除的记录和本条记录都清空\n",
    "        elif record[0] in (\"buy\", \"sell\"):\n",
    "            record[1] = float(record[1])  # 价格\n",
    "            record[2] = int(record[2])  # 数量\n",
    "    for i in reversed(range(len(records))):  # 删除撤销记录\n",
    "        # print(i,records[i])\n",
    "        if records[i][0] == \"\":\n",
    "            records.remove(records[i])\n",
    "    # print(records)\n",
    "    # 构建buy，sell字典\n",
    "    records.sort(key=(lambda x: x[1]), reverse=True)  # 根据价格从大到小排序\n",
    "    buy_list = {}\n",
    "    last_buy = 0\n",
    "    for bs, price, count in records:\n",
    "        if bs == \"buy\":\n",
    "            last_buy += count\n",
    "        buy_list[price] = last_buy  # 存入字典\n",
    "    sell_list = {}\n",
    "    last_sell = 0\n",
    "    for bs, price, count in records[::-1]:  # 价格从小到大\n",
    "        if bs == \"sell\":\n",
    "            last_sell += count\n",
    "        sell_list[price] = last_sell\n",
    "    # 求竞价结果\n",
    "    prices = list(buy_list)\n",
    "    max_amount = 0\n",
    "    best_price = 0\n",
    "    for price in prices:\n",
    "        if min(buy_list[price], sell_list[price]) > max_amount:  # 买入和卖出两者的最小值为成交数\n",
    "            best_price = price\n",
    "            max_amount = min(buy_list[price], sell_list[price])  # 记录当前最大成交数\n",
    "    print(\"{:.2f} {}\".format(best_price, max_amount))\n",
    "\n",
    "\n",
    "# 集合竞价()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 节日\n",
    "\n",
    "试题编号：\t201503-3  \n",
    "试题名称：\t节日\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "month0 = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]  # 平年每月天数\n",
    "month1 = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]  # 闰年每月的天数\n",
    "\n",
    "\n",
    "def is_leap_year(y):\n",
    "    \"\"\"判断是否为闰年\"\"\"\n",
    "    if y % 4 == 0 and y % 100 != 0 or y % 400 == 0:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "\n",
    "def week(y, m, d):\n",
    "    \"\"\"判断y年m月第d天为周几\"\"\"\n",
    "    day_sum = 0\n",
    "    for i in range(1850, y):\n",
    "        if is_leap_year(i):\n",
    "            day_sum += 366\n",
    "        else:\n",
    "            day_sum += 365\n",
    "    month = []\n",
    "    if is_leap_year(y):\n",
    "        month[:] = month1\n",
    "        for i in range(1, m):\n",
    "            day_sum += month[i - 1]\n",
    "    else:\n",
    "        month[:] = month0\n",
    "        for i in range(1, m):\n",
    "            day_sum += month[i - 1]\n",
    "    day_sum += d\n",
    "    day_sum = (day_sum + 1) % 7\n",
    "    return day_sum\n",
    "\n",
    "\n",
    "def 节日():\n",
    "    l1 = [int(x) for x in input().split()]\n",
    "    l1[2] = 0 if l1[2] == 7 else l1[2]\n",
    "    for i in range(l1[3], l1[4] + 1):\n",
    "        if is_leap_year(i):\n",
    "            month = month1[l1[0] - 1]\n",
    "        else:\n",
    "            month = month0[l1[0] - 1]\n",
    "        weekday = week(i, l1[0], 1)  # 存储month月的第一天为周几\n",
    "        a = 0\n",
    "        for j in range(month):\n",
    "            if (weekday + j) % 7 == l1[2]:\n",
    "                a += 1\n",
    "                if a == l1[1]:\n",
    "                    b = str(l1[0]).zfill(2)  # 将字符串的长度填充为2，例如：'1'.zfill(2),输出为'01'\n",
    "                    d = str(j + 1).zfill(2)\n",
    "                    c = [str(i), '/', b, '/', d]\n",
    "                    print(''.join(c))\n",
    "        if a < l1[1]:\n",
    "            print('none')\n",
    "\n",
    "\n",
    "# 节日()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 模板生成系统\n",
    "\n",
    "试题编号：\t201509-3  \n",
    "试题名称：\t模板生成系统\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#!/usr/bin/python3\n",
    "# -*- coding:utf-8 -*-\n",
    "\"\"\"\n",
    "@author: Vigilr\n",
    "@file: 模板生成系统.py\n",
    "@date: 2020-09-01\n",
    "@Editor: PyCharm\n",
    "@desc: \n",
    "\"\"\"\n",
    "# 模板生成系统\n",
    "# re正则表达式匹配\n",
    "import re\n",
    "\n",
    "\n",
    "def 模板生成系统():\n",
    "    global var_dict\n",
    "    m, n = map(int, input().split())\n",
    "    temple = []  # 模板\n",
    "    for i in range(m):\n",
    "        temple.append(input())\n",
    "    var_dict = dict()  # 变量\n",
    "    for i in range(n):\n",
    "        var, value = input().split(\" \", 1)\n",
    "        var_dict[var] = eval(value)  # 清除引号\n",
    "\n",
    "    def trans(matched):  # 变量替换值函数\n",
    "        var = matched.group('var')\n",
    "        if var in var_dict:\n",
    "            return var_dict[var]\n",
    "        else:\n",
    "            return \"\"\n",
    "\n",
    "    for i in range(len(temple)):\n",
    "        print(re.sub(r'{{ (?P<var>\\w*) }}', trans, temple[i]))\n",
    "        # re替换方法，匹配{{  }}格式(?P<var>)命名组，\\w匹配小写字母数字和下划线，*表示匹配一个或多个\\w\n",
    "        # trans匹配方法，调用函数将命名组的var替换成值\n",
    "\n",
    "\n",
    "# 模板生成系统()\n",
    "\n",
    "# 11 2\n",
    "# <!DOCTYPE html>\n",
    "# <html>\n",
    "# <head>\n",
    "# <title>User {{ name }}</title>\n",
    "# </head>\n",
    "# <body>\n",
    "# <h1>{{ name }}</h1>\n",
    "# <p>Email: <a href=\"mailto:{{ email }}\">{{ email }}</a></p>\n",
    "# <p>Address: {{ address }}</p>\n",
    "# </body>\n",
    "# </html>\n",
    "# name \"David Beckham\"\n",
    "# email \"david@beckham.com\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 画图\n",
    "\n",
    "试题编号：\t201512-3  \n",
    "试题名称：\t画图\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def 画图():\n",
    "    global list1, list2, bfs, n, m, artwork\n",
    "    list1 = [[1, 0], [-1, 0], [0, 1], [0, -1]]  # 定义列表使得bfs可以向四周搜索\n",
    "    list2 = ['-', '|', '+', 'XXX']  # 定义列表填作为是否填充的判断\n",
    "\n",
    "    def bfs(x, y, c):  # 定义广度搜索函数\n",
    "        for i in list1:\n",
    "            xx = i[0] + x\n",
    "            yy = i[1] + y\n",
    "            if xx >= n or xx < 0 or yy < 0 or yy >= m or artwork[yy][xx] in list2:\n",
    "                continue\n",
    "            artwork[yy][xx] = c\n",
    "            bfs(xx, yy, c)\n",
    "\n",
    "    n, m, p = map(int, input().split())\n",
    "    artwork = [[\".\" for i in range(n)] for j in range(m)]\n",
    "    for i in range(p):\n",
    "        list3 = input().split()\n",
    "        if int(list3[0]) == 0:\n",
    "            list3 = [int(x) for x in list3]\n",
    "            if list3[1] == list3[3]:\n",
    "                for j in range(min(list3[2], list3[4]), max(list3[2], list3[4]) + 1):\n",
    "                    if artwork[j][list3[1]] == '-' or artwork[j][list3[1]] == '+':\n",
    "                        artwork[j][list3[1]] = '+'\n",
    "                    else:\n",
    "                        artwork[j][list3[1]] = '|'\n",
    "            else:\n",
    "                for j in range(min(list3[1], list3[3]), max(list3[1], list3[3]) + 1):\n",
    "                    if artwork[list3[2]][j] == '|' or artwork[list3[2]][j] == '+':\n",
    "                        artwork[list3[2]][j] = '+'\n",
    "                    else:\n",
    "                        artwork[list3[2]][j] = '-'\n",
    "        else:\n",
    "            list2[3] = list3[3]\n",
    "            bfs(int(list3[1]), int(list3[2]), list3[3])\n",
    "    for i in range(m):\n",
    "        for j in artwork[m - 1 - i]:\n",
    "            print(j, end=\"\")\n",
    "        print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以上为90分的代码，下面是满分的Java代码\n",
    "\n",
    "```java\n",
    "import java.util.Scanner;\n",
    " \n",
    "public class Main {\n",
    "\tpublic static final int N = 105;\n",
    "\tstatic char graph[][] = new char[N][N];\n",
    "\tstatic void dfs(int x, int y, char c,int hei,int wid) {\n",
    "\t\tif (x >= 0&&x < hei && y < wid && y >= 0 && graph[x][y] != '+' && graph[x][y] != '|' && graph[x][y] != '-'&&graph[x][y] != c) {\n",
    "\t\t\tgraph[x][y] = c;\n",
    "\t\t\tdfs(x + 1, y, c,hei,wid);\n",
    "\t\t\tdfs(x - 1, y, c,hei,wid);\n",
    "\t\t\tdfs(x, y + 1, c,hei,wid);\n",
    "\t\t\tdfs(x, y - 1, c,hei,wid);\n",
    "\t\t}\n",
    "\t}\n",
    " \n",
    "\tstatic void line(int x1, int y1, int x2, int y2) {\n",
    "\t\tif (x1 == x2) {\n",
    "\t\t\tint h1 = Math.min(y1, y2);\n",
    "\t\t\tint h2 = Math.max(y1, y2);\n",
    " \n",
    "\t\t\tfor (int j = h1; j <= h2; j++) {\n",
    "\t\t\t\tif (graph[j][x1] == '.' || graph[j][x1] == '|')\n",
    "\t\t\t\t\tgraph[j][x1] = '|';\n",
    "\t\t\t\telse\n",
    "\t\t\t\t\tgraph[j][x1] = '+';\n",
    "\t\t\t}\n",
    "\t\t}\n",
    "\t\tif (y1 == y2) {\n",
    "\t\t\tint h1 = Math.min(x1, x2);\n",
    "\t\t\tint h2 = Math.max(x1, x2);\n",
    "\t\t\tfor (int j = h1; j <= h2; j++) {\n",
    "\t\t\t\tif (graph[y1][j] == '.' || graph[y1][j] == '-')\n",
    "\t\t\t\t\tgraph[y1][j] = '-';\n",
    "\t\t\t\telse\n",
    "\t\t\t\t\tgraph[y1][j] = '+';\n",
    "\t\t\t}\n",
    "\t\t}\n",
    "\t}\n",
    " \n",
    "\tpublic static void main(String[] args) {\n",
    "\t\tScanner scanner = new Scanner(System.in);\n",
    "\t\tint wid = scanner.nextInt();\n",
    "\t\tint hei = scanner.nextInt();\n",
    "\t\tint n = scanner.nextInt();\n",
    "\t\tfor (int i = 0; i < hei; i++) {\n",
    "\t\t\tfor (int j = 0; j < wid; j++) {\n",
    "\t\t\t\tgraph[i][j] = '.';\n",
    "\t\t\t}\n",
    "\t\t}\n",
    "\t\tfor (int k = 0; k < n; k++) {\n",
    "\t\t\tint op = scanner.nextInt();\n",
    "\t\t\tif (op == 0) {\n",
    "\t\t\t\tint x1 = scanner.nextInt();\n",
    "\t\t\t\tint y1 = scanner.nextInt();\n",
    "\t\t\t\tint x2 = scanner.nextInt();\n",
    "\t\t\t\tint y2 = scanner.nextInt();\n",
    "\t\t\t\tline(x1, y1, x2, y2);\n",
    "\t\t\t} else {\n",
    "\t\t\t\tint x = scanner.nextInt();\n",
    "\t\t\t\tint y = scanner.nextInt();\n",
    "\t\t\t\tchar c = scanner.next().charAt(0);\n",
    "\t\t\t\tdfs(y, x, c,hei,wid);\t\n",
    "\t\t\t}\n",
    "\t\t}\n",
    " \n",
    "\t\tfor (int i = hei - 1; i >= 0; i--) {\n",
    "\t\t\tfor (int j = 0; j < wid; j++) {\n",
    "\t\t\t\tSystem.out.print(graph[i][j]);\n",
    "\t\t\t}\n",
    "\t\t\tSystem.out.println();\n",
    "\t\t}\n",
    "\t}\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 路径解析\n",
    "\n",
    "试题编号：\t201604-3  \n",
    "试题名称：\t路径解析\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def 路径解析():\n",
    "    n = int(input())\n",
    "    pwd = input()  # 当前目录\n",
    "    for i in range(n):\n",
    "        route = input()\n",
    "        # re.match()匹配字符串开头\n",
    "        if re.match(\"/\", route) is None:  # 相对路径和空字符串\n",
    "            route = pwd + '/' + route\n",
    "        route += \"/\"  # 结尾加‘/’方便替换，（必须在处理完空串后再加‘/’ ，空串10分）\n",
    "        # re.sub()替换\n",
    "        route = re.sub(r\"//+\", \"/\", route)  # 删去多个‘/’\n",
    "        # 处理[.]\n",
    "        route = re.sub(r\"(/[.])+/\", \"/\", route)  # [.]表示.不转义\n",
    "        # 处理[..]\n",
    "        # re.search()搜索\n",
    "        while re.search(r\"/[.]{2}/\", route):\n",
    "            route = re.sub(r\"^(/[.]{2})+/\", \"/\", route)  # 最开头根目录的上一级还是‘/’,^匹配开头\n",
    "            if \"/../\" in route:  # 文件名不能只用字母数字匹配，要求还有.-_ （10分-20分）\n",
    "                p = route.index(\"/../\")\n",
    "                x = route.rindex(\"/\", 0, p)  # 从0到p范围找，找‘/../’前面的一个‘/’索引也就是上级目录\n",
    "                route = route[0:x] + route[p + 3:]  # 去掉‘/上级目录/../’\n",
    "        while len(route) > 1 and route[-1] == \"/\":  # 去除结尾‘/’\n",
    "            route = route[:-1]\n",
    "        print(route)\n",
    "        \n",
    "# 参考链接：https://blog.csdn.net/SL_logR/article/details/82711605"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 炉石传说\n",
    "\n",
    "试题编号： 201609-3  \n",
    "试题名称： 炉石传说\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class summon:\n",
    "    # 随从类\n",
    "    def __init__(self, position, attack, health):\n",
    "        self.position = position  # 位置，取值[1,7]\n",
    "        self.attack = attack  # 攻击力\n",
    "        self.health = health  # 生命力\n",
    "        self.name = 'summon'  # 表明这是一个随从\n",
    "\n",
    "\n",
    "class attack:\n",
    "    # 攻击类\n",
    "    def __init__(self, first, second):\n",
    "        self.first = first  # 攻击的随从编号，取值[1,7]\n",
    "        self.second = second  # 攻击对象编号，取值[0,7]，其中0表示攻击英雄\n",
    "        self.name = 'attack'  # 表明攻击操作\n",
    "\n",
    "\n",
    "class player:\n",
    "    # 英雄类\n",
    "    def __init__(self):\n",
    "        self.health = 30  # 英雄生命力\n",
    "        self.attack = 0  # 英雄的攻击力，没有用到\n",
    "        self.people = []  # 英雄所拥有的随从\n",
    "#    def fight(self)\n",
    "\n",
    "\n",
    "def 炉石传说():\n",
    "    global two\n",
    "    n = int(input())\n",
    "    data = []\n",
    "    one = player()\n",
    "    two = player()\n",
    "    flag = 1  # 标记哪个英雄进行操作\n",
    "    # 读取、预处理键盘输入数据\n",
    "    for i in range(n):\n",
    "        temp = input().split()\n",
    "        if temp[0] == \"summon\":\n",
    "            data.append(summon(int(temp[1]), int(temp[2]), int(temp[3])))\n",
    "        elif temp[0] == 'attack':\n",
    "            data.append(attack(int(temp[1]), int(temp[2])))\n",
    "        else:\n",
    "            data.append(temp[0])\n",
    "    # 运行用户输入的操作\n",
    "    for i in range(n):\n",
    "        if flag == 1:  # 先出英雄操作\n",
    "            if data[i] == 'end':\n",
    "                flag = 2\n",
    "            else:\n",
    "                if data[i].name == 'summon':  # 上随从\n",
    "                    one.people.insert(data[i].position - 1, data[i])\n",
    "                elif data[i].name == 'attack':  # 攻击\n",
    "                    if data[i].second == 0:\n",
    "                        two.health = two.health - one.people[data[i].first - 1].attack\n",
    "                    else:  # 注意，要把两者攻击后的随从生命算出来后，再检测随从是否消失\n",
    "                        one.people[data[i].first - 1].health -= two.people[data[i].second - 1].attack\n",
    "                        two.people[data[i].second - 1].health -= one.people[data[i].first - 1].attack\n",
    "                        if two.people[data[i].second - 1].health <= 0:\n",
    "                            two.people.pop(data[i].second - 1)\n",
    "                        if one.people[data[i].first - 1].health <= 0:\n",
    "                            one.people.pop(data[i].first - 1)\n",
    "        else:\n",
    "            if data[i] == 'end':\n",
    "                flag = 1\n",
    "            else:\n",
    "                if data[i].name == 'summon':\n",
    "                    two.people.insert(data[i].position - 1, data[i])\n",
    "                elif data[i].name == 'attack':\n",
    "                    if data[i].second == 0:\n",
    "                        one.health = one.health - two.people[data[i].first - 1].attack\n",
    "                    else:\n",
    "                        two.people[data[i].first - 1].health -= one.people[data[i].second - 1].attack\n",
    "                        one.people[data[i].second - 1].health -= two.people[data[i].first - 1].attack\n",
    "                        if one.people[data[i].second - 1].health <= 0:\n",
    "                            one.people.pop(data[i].second - 1)\n",
    "                        if two.people[data[i].first - 1].health <= 0:\n",
    "                            two.people.pop(data[i].first - 1)\n",
    "    if one.health <= 0:\n",
    "        print(-1)\n",
    "    elif two.health <= 0:\n",
    "        print(1)\n",
    "    elif one.health > 0 and two.health > 0:\n",
    "        print(0)\n",
    "    print(one.health)\n",
    "    length = len(one.people)\n",
    "    if length == 0:\n",
    "        print(0)\n",
    "    else:\n",
    "        temp = [length]\n",
    "        for i in one.people:\n",
    "            temp.append(i.health)\n",
    "        print(\" \".join(map(str, temp)))\n",
    "    print(two.health)\n",
    "    length = len(two.people)\n",
    "    if length == 0:\n",
    "        print(0)\n",
    "    else:\n",
    "        temp = [length]\n",
    "        for i in two.people:\n",
    "            temp.append(i.health)\n",
    "        print(\" \".join(map(str, temp)))\n",
    "\n",
    "\n",
    "# 炉石传说()\n",
    "# 参考链接：https://blog.csdn.net/qq_34950042/article/details/88380948"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 权限查询\n",
    "\n",
    "试题编号：\t201612-3  \n",
    "试题名称：\t权限查询\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def 权限查询():\n",
    "    pris = {}  # privileges\n",
    "    roles = {}\n",
    "    users = {}\n",
    "    # 权限\n",
    "    p = int(input())\n",
    "    for i in range(p):\n",
    "        s = input().split(\":\")\n",
    "        pris[s[0]] = s[1] if len(s) == 2 else \"\"  # 因为保证合法性所以其实不用写这段\n",
    "    # 角色\n",
    "    r = int(input())\n",
    "    for i in range(r):\n",
    "        s = input().split()\n",
    "        n = int(s[1])  # 角色权限个数\n",
    "        mypri = []\n",
    "        for j in range(2, 2 + n):\n",
    "            mypri.append(s[j].split(\":\"))\n",
    "        roles[s[0]] = mypri  # 以列表储存\n",
    "    # 用户\n",
    "    u = int(input())\n",
    "    for i in range(u):\n",
    "        s = input().split()\n",
    "        n = int(s[1])  # 用户角色个数\n",
    "        myrole = []\n",
    "        for j in range(2, 2 + n):\n",
    "            myrole.append(s[j])\n",
    "        mypri = {}\n",
    "        for role in myrole:  # 遍历用户\n",
    "            for pri in roles[role]:  # 遍历每个用户权限\n",
    "                if len(pri) == 1:  # 无等级权限\n",
    "                    mypri[pri[0]] = \"\"\n",
    "                elif pri[0] not in mypri:  # 等级权限首次存储\n",
    "                    mypri[pri[0]] = int(pri[1])\n",
    "                else:  # 比较存入权限最大等级\n",
    "                    mypri[pri[0]] = max(mypri[pri[0]], int(pri[1]))\n",
    "        users[s[0]] = mypri  # 用字典存储\n",
    "    # 查询\n",
    "    q = int(input())\n",
    "    for i in range(q):\n",
    "        name, this_pri = input().split()  # 用户名，权限\n",
    "        this_pri = this_pri.split(\":\")  # 区分是否有等级\n",
    "\n",
    "        if name in users:  # 用户存在\n",
    "            if this_pri[0] in users[name]:  # 权限名存在\n",
    "                if len(this_pri) == 1:\n",
    "                    if users[name][this_pri[0]] == \"\":  # 无等级权限\n",
    "                        print(\"true\")\n",
    "                    else:\n",
    "                        print(users[name][this_pri[0]])  # 查询等级\n",
    "                elif len(this_pri) == 2:  # 带等级\n",
    "                    if users[name][this_pri[0]] == \"\":  # 无效查询\n",
    "                        print(\"false\")\n",
    "                    elif int(this_pri[1]) <= users[name][this_pri[0]]:  # 等级满足\n",
    "                        print(\"true\")\n",
    "                    else:  # 等级不满足\n",
    "                        print(\"false\")\n",
    "            else:\n",
    "                print(\"false\")\n",
    "        else:\n",
    "            print(\"false\")\n",
    "\n",
    "\n",
    "# 权限查询()\n",
    "# 参考链接：https://blog.csdn.net/SL_logR/article/details/82711807"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Markdown\n",
    "\n",
    "试题编号：\t201703-3  \n",
    "试题名称：\tMarkdown\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "\n",
    "def Markdown():\n",
    "    data = []  # 记录Markdown转化为html后的文档，data中的一个元素代表html的一行（除开''）\n",
    "    flag = False  # 标记段落是否多行\n",
    "    list_tag = False  # 标记无序列表是否多行\n",
    "    for line in sys.stdin:  # line代表键盘输入的每行内容\n",
    "        # 区块\n",
    "        line = line.strip()\n",
    "        if '#' in line:  # 标题\n",
    "            count = line.count(\"#\")  # 计算是第几标题\n",
    "            temp = line.split('#')[-1].strip()  # 这里分割最好不要用“空格”防止标题含有空格\n",
    "            temp = \"<h\" + str(count) + \">\" + temp + \"</h\" + str(count) + \">\"\n",
    "        elif '*' in line:  # 无序列表\n",
    "            if not list_tag:\n",
    "                data.append('<ul>')\n",
    "                list_tag = True\n",
    "            temp = line.split(\"*\")[-1].strip()  # 采用“*”分割\n",
    "            temp = \"<li>\" + temp + \"</li>\"\n",
    "        else:  # 段落\n",
    "            if line and not flag:  # 首次出现段落\n",
    "                temp = '<p>' + line\n",
    "                flag = True\n",
    "            elif line and flag:  # 中间出现段落\n",
    "                temp = line\n",
    "            elif line == '' and flag:  # 段落结束，修改data最后一个元素的值（即加上'</p>'）\n",
    "                data[-1] = data[-1] + '</p>'\n",
    "                flag = False\n",
    "                temp = ''\n",
    "            elif line == '' and list_tag:  # 无序列表结束\n",
    "                data.append(\"</ul>\")\n",
    "                temp = \"\"\n",
    "                list_tag = False\n",
    "            else:\n",
    "                temp = ''\n",
    "                flag = False\n",
    "                list_tag = False\n",
    "\n",
    "        # 行内\n",
    "\n",
    "        # 强调\n",
    "        i = 1  # 标记是第一个\"_\"，还是第二个\n",
    "        while '_' in temp:  # 注意强调以及超链接都可能多个，所以用无限循环\n",
    "            index_1 = temp.find('_')\n",
    "            if i == 1:\n",
    "                temp = temp[:index_1] + '<em>' + temp[index_1 + 1:]\n",
    "                i = 2\n",
    "            else:\n",
    "                temp = temp[:index_1] + '</em>' + temp[index_1 + 1:]\n",
    "                i = 1\n",
    "        # 超链接\n",
    "        while '[' in temp:  # 注意这里是while，可能有多个超链接\n",
    "            i1 = temp.find('[')\n",
    "            i2 = temp.find(']', i1 + 1)\n",
    "            i3 = temp.find('(', i2 + 1)\n",
    "            i4 = temp.find(')', i3 + 1)\n",
    "            temp = temp[:i1] + '<a href=\"' + temp[(i3 + 1):i4] + '\">' + temp[(i1 + 1):i2] + \"</a>\" + temp[(i4 + 1):]\n",
    "\n",
    "        data.append(temp)  # 将转化后的html加入data\n",
    "    if flag:  # 当以段落结束时\n",
    "        data[-1] = data[-1] + '</p>'\n",
    "    if list_tag:  # 当以无序列表结束时\n",
    "        data.append(\"</ul>\")\n",
    "    for d in data:\n",
    "        if d == '':\n",
    "            continue\n",
    "        print(d)\n",
    "\n",
    "\n",
    "# Markdown()\n",
    "# 参考链接：https://blog.csdn.net/qq_34950042/article/details/88427915"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## JSON查询\n",
    "\n",
    "试题编号：\t201709-3  \n",
    "试题名称：\tJSON查询\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "import json  # python 有内置json库\n",
    "\n",
    "\n",
    "def JSOIN查询():\n",
    "    n, m = map(int, input().split())\n",
    "    # json解析\n",
    "    json_str = \"\"\n",
    "    for i in range(n):\n",
    "        json_str += input()\n",
    "    data = json.loads(json_str)  # json字符串加载为字典\n",
    "    querys = []\n",
    "    for i in range(m):\n",
    "        querys.append(input().split(\".\"))  # 根据.划分层次\n",
    "    json_type = {\n",
    "        str: \"STRING\",\n",
    "        dict: \"OBJECT\"\n",
    "    }\n",
    "    for q in querys:\n",
    "        try:  # 检查字典项的类型，将每个层次带入查询转为字符串 data[\"a\"][\"b\"]并eval()执行\n",
    "            if type(eval(\"data\" + \"\".join([\"[\" + repr(x) + \"]\" for x in q]))) == str:\n",
    "                print(\"STRING\", eval(\"data\" + \"\".join([\"[\" + repr(x) + \"]\" for x in q])))\n",
    "            elif type(eval(\"data\" + \"\".join([\"[\" + repr(x) + \"]\" for x in q]))) == dict:\n",
    "                print(\"OBJECT\")\n",
    "        except Exception:  # 出现异常表示不存在\n",
    "            print(\"NOTEXIST\")\n",
    "\n",
    "\n",
    "# JSOIN查询()\n",
    "# 参考链接：https://blog.csdn.net/SL_logR/article/details/82711846"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Crontab\n",
    "\n",
    "试题编号：\t201712-3  \n",
    "试题名称：\tCrontab\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "Days_of_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]\n",
    "Days_of_mons_in_leap_year = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]\n",
    "Month_string_list = ['Jan', 'Feb', 'Mar', 'Apr', 'May', 'Jun', 'Jul', 'Aug', 'Sep', 'Oct', 'Nov', 'Dec']\n",
    "Weekday_string_list = ['Sun', 'Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat']\n",
    "\n",
    "\n",
    "def m_string2int(m):\n",
    "    try:\n",
    "        a = int(m)\n",
    "        return a\n",
    "    except:\n",
    "        for i in range(12):\n",
    "            if m.lower() == Month_string_list[i].lower():\n",
    "                return i + 1\n",
    "\n",
    "\n",
    "def w_string2int(w):\n",
    "    try:\n",
    "        a = int(w)\n",
    "        return a\n",
    "    except:\n",
    "        for i in range(7):\n",
    "            if w.lower() == Weekday_string_list[i].lower():\n",
    "                return i\n",
    "\n",
    "\n",
    "def ddmm(day, mon):\n",
    "    # d为输入天的字符串，m为输入月份的字符串\n",
    "    # start为开始的天，end为结束的天\n",
    "    # 函数返回所有符合条件的天的list\n",
    "    day_mon_set = []\n",
    "    dayset = []\n",
    "    days = day.split(',')\n",
    "    for d in days:\n",
    "        if d == '*':\n",
    "            dayset = list(i + 1 for i in range(31))\n",
    "        elif len(d.split('-')) != 1:\n",
    "            s, e = list(map(int, d.split('-')))\n",
    "            for i in range(s, e + 1):\n",
    "                dayset.append(i)\n",
    "        else:\n",
    "            dayset.append(int(d))\n",
    "    mons = mon.split(',')\n",
    "    monset = []\n",
    "    for m in mons:\n",
    "        if m == '*':\n",
    "            monset = list(i + 1 for i in range(12))\n",
    "        elif len(m.split('-')) != 1:\n",
    "            s, e = m.split('-')\n",
    "            for i in range(m_string2int(s), m_string2int(e) + 1):\n",
    "                monset.append(i)\n",
    "        else:\n",
    "            monset.append(m_string2int(m))\n",
    "    for x in monset:\n",
    "        for y in dayset:\n",
    "            day_mon_set.append(x * 100 + y)\n",
    "    return day_mon_set\n",
    "\n",
    "\n",
    "def MMHH(mm, hh):\n",
    "    min_hour_set = []\n",
    "    minset = []\n",
    "    hourset = []\n",
    "    mms = mm.split(',')\n",
    "    for m in mms:\n",
    "        if m == '*':\n",
    "            minset = list(i for i in range(60))\n",
    "        elif len(m.split('-')) != 1:\n",
    "            s, e = list(map(int, m.split('-')))\n",
    "            for i in range(s, e + 1):\n",
    "                minset.append(i)\n",
    "        else:\n",
    "            minset.append(int(m))\n",
    "    hhs = hh.split(',')\n",
    "    for h in hhs:\n",
    "        if h == '*':\n",
    "            hourset = list(i for i in range(24))\n",
    "        elif len(h.split('-')) != 1:\n",
    "            s, e = list(map(int, h.split('-')))\n",
    "            for i in range(s, e + 1):\n",
    "                hourset.append(i)\n",
    "        else:\n",
    "            hourset.append(int(h))\n",
    "    for h in hourset:\n",
    "        for m in minset:\n",
    "            min_hour_set.append(h * 100 + m)\n",
    "    return min_hour_set\n",
    "\n",
    "\n",
    "def day_of_week(ww):\n",
    "    if ww == '*':\n",
    "        return list(i for i in range(7))\n",
    "    else:\n",
    "        dset = []\n",
    "        wws = ww.split(',')\n",
    "        for w in wws:\n",
    "            if len(w.split('-')) != 1:\n",
    "                s, e = w.split('-')\n",
    "                for i in range(w_string2int(s), w_string2int(e) + 1):\n",
    "                    dset.append(i)\n",
    "            else:\n",
    "                dset.append(w_string2int(w))\n",
    "        return dset\n",
    "\n",
    "\n",
    "def check(ymhdmw):\n",
    "    normal = []\n",
    "    for X in ymhdmw:\n",
    "        year, mon_day, hour_min, weekday, com = X\n",
    "        # 检查是否在设置的时间范围内\n",
    "        time = year * 100000000 + mon_day * 10000 + hour_min\n",
    "        if time < start or time >= end:\n",
    "            continue\n",
    "\n",
    "        # 检查每个月的日期数是否正常\n",
    "        if (year % 4) == 0:\n",
    "            daysbefore = sum(Days_of_mons_in_leap_year[0:mon_day // 100 - 1])\n",
    "            if (Days_of_mons_in_leap_year[mon_day // 100 - 1] < (mon_day % 100)):\n",
    "                continue\n",
    "        else:\n",
    "            daysbefore = sum(Days_of_month[0:mon_day // 100 - 1])\n",
    "            if Days_of_month[mon_day // 100 - 1] < (mon_day % 100):\n",
    "                continue\n",
    "\n",
    "        # 检查星期数是否正常\n",
    "        years_from_1970 = year - 1970\n",
    "        num_of_leap_year = (years_from_1970 + 1) // 4\n",
    "        days_from_197011 = years_from_1970 * 365 + num_of_leap_year + daysbefore + mon_day % 100 - 1\n",
    "        if ((days_from_197011 % 7) + 4) % 7 == weekday:\n",
    "            normal.append([time, command])\n",
    "    return normal\n",
    "\n",
    "\n",
    "def Crontab():\n",
    "    global start, end, command\n",
    "    n, start, end = list(map(int, input().split()))\n",
    "    crontab = []\n",
    "    startyear = start // 100000000\n",
    "    endyear = end // 100000000\n",
    "    for i in range(n):\n",
    "        minutes, hours, day_of_month, month, dayofweek, command = input().split()\n",
    "        minhoueset = MMHH(minutes, hours)\n",
    "        daymonset = ddmm(day_of_month, month)\n",
    "        week = day_of_week(dayofweek)\n",
    "        ymhdmw = []\n",
    "        for i in range(startyear, endyear + 1):\n",
    "            for mh in minhoueset:\n",
    "                for dm in daymonset:\n",
    "                    for w in week:\n",
    "                        ymhdmw.append([i, dm, mh, w, command])\n",
    "        crontab.append(check(ymhdmw))\n",
    "    crontab1 = []\n",
    "    for X in crontab:\n",
    "        for x in X:\n",
    "            crontab1.append(x)\n",
    "    crontab2 = sorted(crontab1, key=lambda x: x[0])\n",
    "    for i in crontab2:\n",
    "        print(i[0], i[1])\n",
    "\n",
    "\n",
    "# Crontab()\n",
    "# 参考链接：https://blog.csdn.net/qq_41564189/article/details/100639481"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## URL映射\n",
    "\n",
    "试题编号：\t201803-3  \n",
    "试题名称：\tURL映射\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def URL映射():\n",
    "    m, n = map(int, input().split())\n",
    "    rules = {}\n",
    "    rlist = {}\n",
    "    for i in range(m):\n",
    "        rule, name = input().split()\n",
    "        rlist[rule] = rule.split(\"/\")\n",
    "        rules[rule] = name\n",
    "    for i in range(n):\n",
    "        query = input()\n",
    "        q = query.split(\"/\")\n",
    "        find = False\n",
    "        for rule in rules.keys():\n",
    "            r = rlist[rule]\n",
    "            if len(q) >= len(r):\n",
    "                args = []\n",
    "                match = 0\n",
    "                RightPath = False\n",
    "                for j in range(len(r)):\n",
    "                    if q[j] == r[j]:\n",
    "                        match += 1\n",
    "\n",
    "                    elif q[j].isdigit() and r[j] == \"<int>\":\n",
    "                        args.append(str(int(q[j])))\n",
    "                        match += 1\n",
    "\n",
    "                    elif r[j] == \"<str>\":\n",
    "                        if q[j] == \"\":  # 加了这个判断就100分了 ?!空字符串对应<str>\n",
    "                            break\n",
    "                        args.append(q[j])\n",
    "                        match += 1\n",
    "\n",
    "                    elif r[j] == \"<path>\":\n",
    "                        args.append(\"/\".join(q[len(r) - 1:]))\n",
    "                        RightPath = True\n",
    "                        match += 1\n",
    "\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "                if match == len(r) and (len(q) == len(r) or RightPath):\n",
    "                    print(rules[rule] + \" \" + \" \".join(args))\n",
    "                    find = True\n",
    "                    break\n",
    "            else:\n",
    "                continue\n",
    "        if not find:\n",
    "            print(\"404\")\n",
    "\n",
    "\n",
    "# URL映射()\n",
    "# 参考链接：https://blog.csdn.net/SL_logR/article/details/82711977"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 元素选择器\n",
    "\n",
    "试题编号：\t201809-3  \n",
    "试题名称：\t元素选择器\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def 元素选择器():\n",
    "    # 元素选择器\n",
    "    # 输入\n",
    "    n, m = map(int, input().split())\n",
    "    doc = []\n",
    "    sel = []\n",
    "    # 结构化文档内容\n",
    "    for i in range(n):\n",
    "        doc.append(input())\n",
    "    # 带查询的选择器\n",
    "    for i in range(m):\n",
    "        sel.append(input())\n",
    "    # 解析文档结构\n",
    "    cons = []\n",
    "    for i in range(n):\n",
    "        level = doc[i].count('.') // 2\n",
    "        tag = \"\"\n",
    "        tid = \"\"\n",
    "        if len(doc[i].split()) == 1:\n",
    "            tag = doc[i][level * 2:]\n",
    "        else:\n",
    "            left, right = doc[i].split()\n",
    "            tag = left[level * 2:]  # 标签大小写不敏感\n",
    "            tid = right  # id大小写敏感\n",
    "        pline = -1\n",
    "        for j in range(i - 1, 0 - 1, -1):\n",
    "            if cons[j][\"level\"] == level - 1:\n",
    "                pline = j + 1\n",
    "                break\n",
    "        cons.append({\"tag\": tag, \"id\": tid, \"level\": level, \"pline\": pline})  # 将信息存为字典添加到列表中\n",
    "    # 元素选择器选择\n",
    "    collection = []  # 结果保存列表\n",
    "    for i in range(m):\n",
    "        collection.append([])\n",
    "        if len(sel[i].split()) == 1:  # 选择器不含空格\n",
    "            if sel[i][0] != '#':  # 标签选择器\n",
    "                for j in range(n):\n",
    "                    if cons[j][\"tag\"].lower() == sel[i].lower():  # 标签大小写不敏感\n",
    "                        collection[i].append(j + 1)\n",
    "            else:  # id选择器\n",
    "                for j in range(n):\n",
    "                    if cons[j][\"id\"] == sel[i]:  # id大小写敏感\n",
    "                        collection[i].append(j + 1)\n",
    "        else:  # 后代选择器\n",
    "\n",
    "            p = sel[i].split()\n",
    "            for j in range(n):\n",
    "                parent = j + 1\n",
    "                k = len(p) - 1\n",
    "                while k >= 0:  # 从后向前迭代检查是否匹配\n",
    "                    match = False\n",
    "                    if p[k][0] != '#':\n",
    "                        if cons[parent - 1][\"tag\"].lower() == p[k].lower():\n",
    "                            match = True\n",
    "                        else:\n",
    "                            if parent == j + 1 and k == len(p) - 1:  # 第一次必须匹配上不然直接退出\n",
    "                                break\n",
    "                    else:\n",
    "                        if cons[parent - 1][\"id\"] == p[k]:\n",
    "                            match = True\n",
    "                        else:\n",
    "                            if parent == j + 1 and k == len(p) - 1:\n",
    "                                break\n",
    "                    if match:\n",
    "                        k -= 1\n",
    "                        if k < 0:  # 匹配成功\n",
    "                            collection[i].append(j + 1)\n",
    "                            break\n",
    "                    if cons[parent - 1][\"pline\"] == -1:  # 没有父节点了仍未匹配成功即匹配失败\n",
    "                        break  # 匹配失败退出\n",
    "                    parent = cons[parent - 1][\"pline\"]  # 取父节点继续检查匹配\n",
    "    # 输出\n",
    "    for x in collection:\n",
    "        print(len(x), \" \".join(map(str, x)))\n",
    "\n",
    "\n",
    "# 元素选择器()\n",
    "# 参考链接：https://blog.csdn.net/SL_logR/article/details/82729191"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CIDR合并\n",
    "\n",
    "试题编号：\t201812-3  \n",
    "试题名称：\tCIDR合并\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dvismerge(ip1: tuple, ip2: tuple) -> bool:  # 大小合并\n",
    "    # True 1 > 2\n",
    "    minlen = min(ip1[1], ip2[1])\n",
    "    if ip1[0][:minlen] == ip2[0][:minlen]:  # 等价\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "\n",
    "def vismerge(ip_pre1: tuple, ip_pre2: tuple) -> tuple:  # 同级合并\n",
    "    len1, len2 = ip_pre1[1], ip_pre2[1]\n",
    "    ip1, ip2 = ip_pre1[0], ip_pre2[0]\n",
    "    if len1 == len2 and ip1[:len1 - 1] == ip2[:len1 - 1] and ip1[len1 - 1] != ip2[len1 - 1]:\n",
    "        # 1011-4 & 1010-4 -> 101-3\n",
    "        return True, (ip1[:len1 - 1].ljust(32, '0'), len1 - 1)\n",
    "    else:\n",
    "        return False, 0\n",
    "\n",
    "\n",
    "def formatIP(iplist: list, ip_split: list) -> str:\n",
    "    op = re.compile(r'[\\./]')\n",
    "    for ip in iplist:\n",
    "        d = re.split(op, ip)  # 按.和/拆分\n",
    "        if ip.count(\"/\") is 0:  # 省略长度型\n",
    "            length = len(d)  # 不为为0的长(256)\n",
    "            for _ in range(4 - length):\n",
    "                d.append(\"0\")\n",
    "            d.append(str(length * 8))\n",
    "            ip_split.append(list(map(int, d)))\n",
    "        else:\n",
    "            if len(d) is 5:  # 标准\n",
    "                ip_split.append(list(map(int, d)))\n",
    "            else:  # 省略后缀\n",
    "                length = len(d) - 1  # 不为0的长度(256)\n",
    "                tmp = d[:length]\n",
    "                for _ in range(4 - length):\n",
    "                    tmp.append(\"0\")\n",
    "                tmp.append(d[-1])\n",
    "                ip_split.append(list(map(int, tmp)))\n",
    "\n",
    "\n",
    "def binip(ip_split: list, bin_ip):\n",
    "    for ip in ip_split:\n",
    "        t = ''\n",
    "        for i in range(4):\n",
    "            t += bin(ip[i])[2:].rjust(8, '0')  # 前导补零\n",
    "        bin_ip.append((t, ip[4]))\n",
    "\n",
    "\n",
    "def CIDR合并():\n",
    "    n = int(input())\n",
    "    ip = []\n",
    "    ip_split = []\n",
    "    bin_ip = []  # 二进制补0及长度的元list\n",
    "    for _ in range(n):\n",
    "        ip.append(input())\n",
    "    formatIP(ip, ip_split)  # 格式化\n",
    "    ip_split.sort()  # 排序\n",
    "    binip(ip_split, bin_ip)  # 排好序后的二进制\n",
    "    # 从大到小合并\n",
    "    i = 0\n",
    "    while i < len(bin_ip) - 1:\n",
    "        if dvismerge(bin_ip[i], bin_ip[i + 1]):\n",
    "            del bin_ip[i + 1]\n",
    "            i -= 1\n",
    "        i += 1\n",
    "    # 同级合并\n",
    "    i = 0\n",
    "    while i < len(bin_ip) - 1:\n",
    "        tmpr = vismerge(bin_ip[i], bin_ip[i + 1])\n",
    "        if tmpr[0]:\n",
    "            del bin_ip[i]\n",
    "            del bin_ip[i]\n",
    "            bin_ip.insert(i, tmpr[1])\n",
    "            i -= 2\n",
    "        i += 1\n",
    "    # 输出\n",
    "    for bp, length in bin_ip:\n",
    "        res_ip = '.'.join(list(map(lambda x: str(int(x, 2)),\n",
    "                                   re.findall(r'.{8}', bp)))) + '/' + str(length)\n",
    "        print(res_ip)\n",
    "\n",
    "\n",
    "# CIDR合并()\n",
    "# 参考链接：https://blog.csdn.net/q19149/article/details/99244415"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 损坏的RAID5\n",
    "\n",
    "试题编号：\t201903-3  \n",
    "试题名称：\t损坏的RAID5\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def 损坏的RAID5():\n",
    "    \"\"\"\n",
    "    b//s 条带号\n",
    "    g=b//(s*(n-1)) 组号 校验盘号pid=n-1-g%n\n",
    "    要将块号映射到磁盘号和该磁盘块号\n",
    "    \"\"\"\n",
    "    n, s, l = map(int, input().split())\n",
    "    infod = {}\n",
    "    length = 0\n",
    "    for i in range(l):\n",
    "        k, content = input().split()\n",
    "        infod[k] = content\n",
    "        if i == 0:\n",
    "            length = len(content) // 8 * (n - 1) - 1\n",
    "    m = int(input())\n",
    "    for i in range(m):\n",
    "        b = int(input())  # 块号\n",
    "        if b > length:\n",
    "            print(\"-\")\n",
    "            continue\n",
    "        g = b // (s * (n - 1))  # 组号\n",
    "        pid = n - 1 - g % n  # 该组校验盘号√\n",
    "        d = b % (s * (n - 1))  # 块号转换为0-\n",
    "        did = (d // s + pid + 1) % n  # 磁盘号√\n",
    "        dbid = g * s + b % s  # 在该磁盘的块号√\n",
    "        startbit = dbid * 8\n",
    "        if str(did) not in infod.keys():  # 缺盘\n",
    "            if len(infod.keys()) == n - 1:  # 可计算\n",
    "                c = 0\n",
    "                for j in infod.values():\n",
    "                    c ^= int(j[startbit:startbit + 8], 16)\n",
    "                print(hex(c).upper()[2:])\n",
    "\n",
    "            else:\n",
    "                print(\"-\")\n",
    "        else:\n",
    "            print(infod[str(did)][startbit:startbit + 8])\n",
    "\n",
    "\n",
    "# 损坏的RAID5()\n",
    "# 参考链接：https://blog.csdn.net/qq_39577481/article/details/103225826"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 字符画\n",
    "\n",
    "试题编号：\t201909-3  \n",
    "试题名称：\t字符画\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "defaback = [0, 0, 0]\n",
    "reset = \"[0m\"\n",
    "last = []\n",
    "s = \"\"\n",
    "prefix = \"\\\\x1B\"\n",
    "\n",
    "\n",
    "def solveCol(c):\n",
    "    if len(c) == 2:\n",
    "        c += c[-1] * 6\n",
    "    elif len(c) == 4:\n",
    "        c = \"#\" + c[1] * 2 + c[2] * 2 + c[3] * 2\n",
    "    l = [int(c[i:i + 2], 16) for i in range(1, 7, 2)]\n",
    "    return l\n",
    "\n",
    "\n",
    "# m, n = map(int, input().split())\n",
    "# p, q = map(int, input().split())\n",
    "# colormatrix = [[] for i in range(n)]\n",
    "# for row in range(n):\n",
    "#     for col in range(m):\n",
    "#         colormatrix[row].append(solveCol(input()))\n",
    "#         if (col + 1) % p == 0 and (row + 1) % q == 0:\n",
    "#             srow = row // q\n",
    "#             scol = col // p\n",
    "#             suit = list(\n",
    "#                 zip(*[colormatrix[k][l] for l in range(col - p + 1, col + 1) for k in range(row - q + 1, row + 1)]))\n",
    "\n",
    "#             current = [sum(s) // len(s) for s in suit]\n",
    "\n",
    "#             if srow == 0 and scol == 0:\n",
    "#                 if current != defaback:\n",
    "#                     d = \"[48;2;\" + \";\".join(map(str, current)) + \"m\"\n",
    "#                     t = [\"\\\\x\" + hex(ord(i))[2:].upper().zfill(2) for i in d]\n",
    "#                     s += prefix + \"\".join(t)\n",
    "#             else:\n",
    "#                 if current == last:\n",
    "#                     pass\n",
    "#                 else:\n",
    "#                     if current == defaback:\n",
    "#                         s += \"\\\\x1B\\\\x5B\\\\x30\\\\x6D\"\n",
    "#                     else:\n",
    "#                         d = \"[48;2;\" + \";\".join(map(str, current)) + \"m\"\n",
    "\n",
    "#                         t = [\"\\\\x\" + hex(ord(i))[2:].upper().zfill(2) for i in d]\n",
    "#                         s += prefix + \"\".join(t)\n",
    "#             last = current\n",
    "#             # 空格\n",
    "#             s += \"\\\\x20\"\n",
    "#             # 换行\n",
    "#             if scol == m // p - 1:\n",
    "#                 # 输出每行后判断是否重置\n",
    "#                 if last != defaback:\n",
    "#                     s += \"\\\\x1B\\\\x5B\\\\x30\\\\x6D\"\n",
    "#                     last = defaback\n",
    "\n",
    "#                 s += '''\\\\x0A'''\n",
    "# print(s)\n",
    "\n",
    "# 参考链接：https://blog.csdn.net/qq_39577481/article/details/103225865"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 化学方程式\n",
    "\n",
    "试题编号：\t201912-3  \n",
    "试题名称：\t化学方程式\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "#!/usr/bin/python3\n",
    "# -*- coding:utf-8 -*-\n",
    "\"\"\"\n",
    "@author: Vigilr\n",
    "@file: 化学方程式.py\n",
    "@date: 2020-09-04\n",
    "@Editor: PyCharm\n",
    "@desc: \n",
    "\"\"\"\n",
    "import re\n",
    "\n",
    "pattern_ele = re.compile(r'[A-Z][a-z]?')  # 匹配化学元素的模式\n",
    "pattern_lc = re.compile(r'^\\d+')  # 匹配左边系数的模式\n",
    "pattern_rc = re.compile(r'\\d+$')  # 匹配右边系数的模式\n",
    "pattern_term = re.compile(r'^[A-Z][a-z]?\\d*')  # 匹配化学式中的项(元素部分)和系数\n",
    "# 该函数用于处理系数和化学式\n",
    "'''\n",
    "if:处理测试编号点1-6\n",
    "elif/else:处理测试编号点7-10\n",
    "'''\n",
    "\n",
    "\n",
    "def deal_formula(ceof, formula, dic):\n",
    "    i = 0\n",
    "    while i < len(formula):\n",
    "        term = pattern_term.match(formula[i:])\n",
    "        if term is not None:  # 处理未出现括号的情况\n",
    "            term = term.group()\n",
    "            if term[-1].isdigit():  # 处理如 Na2CO3 的情况\n",
    "                r_ceof = pattern_rc.search(term)[0]\n",
    "                ele = term[:-len(r_ceof)]\n",
    "                deal_ele(ceof * int(r_ceof), ele, dic)\n",
    "            else:  # 处理如 CaCO3 的情况\n",
    "                deal_ele(ceof, term, dic)\n",
    "            i += len(term)\n",
    "\n",
    "        else:  # 处理出现括号以及括号嵌套的情况：如 （NH4)2CO3、Na(Au(CN)2)\n",
    "            begin = i + 1\n",
    "            end = begin\n",
    "            close = 1\n",
    "            while end < len(formula):\n",
    "                if formula[end] == '(':\n",
    "                    close += 1\n",
    "                elif formula[end] == ')':\n",
    "                    close -= 1\n",
    "                if close == 0:\n",
    "                    break\n",
    "                end += 1\n",
    "            if end + 1 < len(formula) and formula[end + 1].isdigit():\n",
    "                r_ceof = pattern_lc.match(formula[end + 1:])[0]\n",
    "                deal_formula(ceof * int(r_ceof), formula[begin:end], dic)\n",
    "                end += len(r_ceof)\n",
    "            else:\n",
    "                deal_formula(ceof, formula[begin:end], dic)\n",
    "            i = end + 1\n",
    "\n",
    "\n",
    "# 处理元素                                 \n",
    "def deal_ele(ceof, element, dic):\n",
    "    dic[element] += ceof\n",
    "\n",
    "\n",
    "# 处理表达式\n",
    "def deal_expr(expr):\n",
    "    ceof = 1\n",
    "    formula = expr\n",
    "    if expr[0].isdigit():\n",
    "        ceof_str = pattern_lc.match(expr)[0]\n",
    "        ceof = int(ceof_str)\n",
    "        formula = expr[len(ceof_str):]\n",
    "    return ceof, formula\n",
    "\n",
    "\n",
    "# 校验化学方程式       \n",
    "def checkEquation(equation):\n",
    "    ele_dic = [{}, {}]\n",
    "    expr_list = [[], []]\n",
    "    exprs = equation.split(\"=\")\n",
    "\n",
    "    for i in range(2):\n",
    "        eles = set(pattern_ele.findall(exprs[i]))\n",
    "        for j in eles:\n",
    "            ele_dic[i][j] = 0\n",
    "\n",
    "    if ele_dic[0] != ele_dic[1]:\n",
    "        print('N')\n",
    "        return None\n",
    "    for i in range(2):\n",
    "        expr_list[i] = exprs[i].split('+')\n",
    "        for j in expr_list[i]:\n",
    "            ceof, formula = deal_expr(j)\n",
    "            deal_formula(ceof, formula, ele_dic[i])\n",
    "    if ele_dic[0] == ele_dic[1]:\n",
    "        print('Y')\n",
    "    else:\n",
    "        print('N')\n",
    "\n",
    "\n",
    "def 化学方程式():\n",
    "    n = int(input())\n",
    "    lists = []\n",
    "    for i in range(n):\n",
    "        equation = input()\n",
    "        lists.append(equation)\n",
    "    for i in lists:\n",
    "        checkEquation(i)\n",
    "\n",
    "\n",
    "# 化学方程式()\n",
    "# 参考链接：https://www.jianshu.com/p/0594a7f5d4ad"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Markdown渲染器\n",
    "\n",
    "试题编号：\t202006-3  \n",
    "试题名称：\tMarkdown渲染器\n",
    "\n",
    "[返回目录](#目录)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 参考链接：https://www.cnblogs.com/137shoebills/p/13615919.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**C++ 的代码题解**\n",
    "\n",
    "```c++\n",
    "#include<bits/stdc++.h>\n",
    "using namespace std;\n",
    "const int maxn=10000010;\n",
    "int myget(char *b){\n",
    "    char ch=getchar();\n",
    "    if(ch==EOF)return -1;\n",
    "    int i=0;\n",
    "    while(ch!='\\n'&&ch!=EOF){\n",
    "        *(b+i)=ch;++i;\n",
    "        ch=getchar();\n",
    "    }return i;\n",
    "}char a[21000000];\n",
    "int main(){\n",
    "    //freopen(\"init2.txt\",\"r\",stdin);\n",
    "    int n,typ=0,lin=1,cnt=0,now=0,lonf=0;\n",
    "    int w;cin>>w;getchar();\n",
    "    int num=0;\n",
    "    // 段落 1，项目 2，无类型0\n",
    "    while((n=myget(a))!=-1){\n",
    "        ++num;//cout<<num<<endl;\n",
    "        int f=0;\n",
    "        for(int i=0;i<n;++i){ if(a[i]!=' '){ f=1;break; } }\n",
    "        //cout<<1<<' '<<lin<<' '<<cnt<<' '<<typ<<' '<<f<<endl;\n",
    "        if(!f){\n",
    "            lonf=1;\n",
    "            continue;\n",
    "        }\n",
    "        if(a[0]=='*'&&a[1]==' '){\n",
    "            if(lonf){\n",
    "                if(now==1){typ=0;cnt=0;lin+=2;}\n",
    "                if(cnt!=0){cnt=0;++lin;}\n",
    "                if(typ!=0){typ=0;++lin;}\n",
    "                lonf=0;\n",
    "            }\n",
    "            if(typ==2){if(cnt!=0||now==1)++lin;}\n",
    "            else if(typ==1){++lin; if(cnt!=0)++lin;}\n",
    "            typ=2; cnt=0; now=0;\n",
    "            int l=0,r=-1;\n",
    "            for(int i=2;i<n;++i)if(a[i]!=' '){l=i;break;}\n",
    "            for(int i=n-1;i>=2;--i)if(a[i]!=' '){r=i;break;}\n",
    "            if(r==-1)now=1;\n",
    "            for(int i=l;i<=r;++i){\n",
    "                if(cnt==0&&a[i]==' ')continue;\n",
    "                if(cnt==0)cnt=3;\n",
    "                ++cnt;\n",
    "                if(cnt==w){cnt=0;++lin;}\n",
    "            }\n",
    "        }\n",
    "        else if(typ==2&&(!lonf)&&a[0]==' '&&a[1]==' '){\n",
    "            int l=0,r=-1;\n",
    "            for(int i=2;i<n;++i)if(a[i]!=' '){l=i;break;}\n",
    "            for(int i=n-1;i>=2;--i)if(a[i]!=' '){r=i;break;}\n",
    "            if(cnt==w-1){++lin;cnt=0;}\n",
    "            else if(cnt!=0)++cnt;\n",
    "            for(int i=l;i<=r;++i){\n",
    "                if(cnt==0&&a[i]==' ')continue;\n",
    "                if(cnt==0)cnt=3;\n",
    "                ++cnt;\n",
    "                if(cnt==w){cnt=0;++lin;}\n",
    "            }\n",
    "        }\n",
    "        else{\n",
    "            if(lonf){\n",
    "                if(now==1){typ=0;cnt=0;lin+=2;}\n",
    "                if(cnt!=0){cnt=0;++lin;}\n",
    "                if(typ!=0){typ=0;++lin;}\n",
    "                lonf=0;\n",
    "            }\n",
    "            if(typ==1){\n",
    "                if(cnt==w-1){++lin;cnt=0;}\n",
    "                else if(cnt!=0)++cnt;\n",
    "            }\n",
    "            else if(typ==0)typ=1;\n",
    "            else{ if(cnt!=0||now)++lin; ++lin;typ=1;cnt=0;}\n",
    "            int l=0,r=-1;now=0;\n",
    "            for(int i=0;i<n;++i)if(a[i]!=' '){l=i;break;}\n",
    "            for(int i=n-1;i>=0;--i)if(a[i]!=' '){r=i;break;}\n",
    "            for(int i=l;i<=r;++i){\n",
    "                if(cnt==0&&a[i]==' ')continue;\n",
    "                ++cnt;\n",
    "                if(cnt==w){cnt=0;++lin;}\n",
    "            }\n",
    "        } //cout<<2<<' '<<lin<<' '<<cnt<<' '<<typ<<endl;\n",
    "    }\n",
    "    if(cnt==0&&!now)--lin;\n",
    "    cout<<lin<<endl;\n",
    "    return 0;\n",
    "}\n",
    "```"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
